'''
https://leetcode.cn/problems/edit-distance/
'''
from functools import cache


class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        @cache
        def f(i, j):
            if i == m and j == n:
                return 0
            if j == n:
                return 1 + f(i+1, n)    # 删除
            if i == m:
                return 1 + f(m, j+1)    # 新增
            if word1[i] == word2[j]:    # 匹配上最好了
                return f(i+1, j+1)
            return 1 + min(f(i+1, j), f(i, j+1), f(i+1, j+1))    # 删除或新增或编辑
        return f(0, 0)
    # dp打表
    def minDistance2(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m-1, -1, -1):
            dp[i][n] = 1 + dp[i+1][n]
        for j in range(n-1, -1, -1):
            dp[m][j] = 1 + dp[m][j+1]
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if word1[i] == word2[j]:    # 匹配上最好了
                    dp[i][j] =  dp[i+1][j+1]
                else:
                    dp[i][j] = 1 + min(dp[i+1][j], dp[i][j+1], dp[i+1][j+1])    # 删除或新增或编辑
        # print(*dp, sep='\n')
        return dp[0][0]

s1 = 'horse'
s2 = 'ros'
print(Solution().minDistance2(s1, s2))